A computer-aided design (CAD) system should account for the dynamic nature of the design process, enabling design modifications while recognizing critical design constraints which should not change. In the past, it was necessary for the CAD engineer to remember the design constraints and relationships and consciously preserve them every time a change is made to the design, increasing both design time and the possibility of error. Maintaining design constraints and relationships is particularly difficult through multiple design changes, particularly with complex parts. Compounding the problem is the fact that even simple designs include hundreds of constraints and all of the design constraints may not be known when a modification is made or attempted. Ideally, a CAD system would allow the engineer to make a design change while maintaining critical constraints, would identify conflicts among the constraints, and possible solutions where the design is overconstrained.
Many design problems can be generally described as a geometric constraint satisfaction problem. That is, given a collection of geometric entities and constraints that describe how the geometric entities interact with each other, find their positions, orientations, and dimensions (i.e., "configuration") so as to satisfy all constraints simultaneously. Solving such geometric constraint satisfaction problems is central to several related domains: describing mechanical assemblies, constraint-based sketching and design, geometric modeling for CAD, and kinematic analysis of robots and other mechanisms. U.S. patent application Nos. 07/365,586; 07/675,592; and U.S. Pat. No. 5,043,929 (incorporated by reference) relate to techniques for solving certain aspects of geometric constraint satisfaction problems.
Known general-purpose constraint satisfaction techniques are not well suited to the solution of constraint problems involving complicated geometry. Existing techniques represent geometric entities and constraints as algebraic equations, whose real solutions yield the numerical values describing the positions, orientations, and dimensions of the geometric entities. Such equation sets are highly nonlinear and highly coupled, and in the general case require iterative numerical solution techniques. Iterative numerical programs are not particularly efficient, and can have problems with stability and robustness. See, William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, Cambridge, UK, 1986. For many tasks (e.g., simulation and optimization of mechanical devices) the same equations are solved repeatedly, which makes a "hard-wired," or compiled, solution desirable.
In theory, symbolic analysis of such complex algebraic equations can often yield a non-iterative, closed-form solution, or can help reduce the number of redundant generalized coordinates in an iterative problem. Once found and compiled, such a closed-form solution may be executed in time nearly linearly proportional to the size of the constraint problem. However, the computational instability and intractability of symbolic algebraic solution of the equations renders this approach impractical. See, Yanxi Liu and Robin J. Poppiestone, Symmetry Constraint Inference in Assembly Planning: Automatic assembly configuration specification. In Proceedings of the National Conference on Artificial Intelligence, pages 1038-1044, Boston, Mass., 1990.
Numerical analysis of these complex algebraic equations include two approaches: "Propagational" and "Variational." Propagational methods are widely used commercially and are commonly known as "parametric." In a propagational method, each geometric entity that makes up a model is placed relative to an entity that was defined before it. Numeric propagational systems keep track of the sequence of geometric entities and their corresponding equations. When modifications are made to the design, the system works its way along a propagational chain to redefine the geometry according to the changes the user has made. This is similar to what happens when a change is made to a cell in a computerized spreadsheet; the modifications are propagated from column to column throughout the rest of the spreadsheet. Propagational methods can be direct and fast, but they have difficulty reconciling simultaneous equations.
Numeric "Variational" methods have also had commercial success. In variational methods, the system asks the user to specify the geometry and the relationships among entities. The system then solves the constraints numerically, using conventional iterative techniques. Variational systems are able to handle a wide range of constraints, including simultaneous equations, but generally speaking, their performance is much slower than propagational methods, and stability and convergence problems often make results unpredictable.
Since such conventional analysis methods take what is essentially geometry and couch it in terms of equations, systems based on these methods cannot truly understand how geometry behaves. Therefore, systems using these methods have difficulty preserving the user's design intent consistently, reliably, and quickly.
Another problem with conventional approaches is deriving a representation of the geometry of the system allowing closed-form solution which facilitates design and analysis. While some problems such as finite element analysis and design using deformable surfaces are inherently iterative in nature, other problems can, in principle, be treated either entirely or in large part using closed-form solution techniques. See, George Celniker and David Gossard, Deformable Curve and Surface Finite-Elements for Free-Form Shape Design, Computer Graphics, 25(4):257-266, July 1991 and Richard H. Gallagher. Finite Element Analysis: Fundamentals. Prentice-Hall, Inc., Englewood Cliffs, N.J., 1975. In practice, problems amenable to closed-form solution are still treated iteratively, either due to the complexity of deriving a direct formulation, or due to the use of more general solution techniques that also handle the (possibly small) portions of the problem which require iteration.
Domains such as constraint-based sketching and mechanical part design are amenable to closed-form solution. They tend to rely on complex combinations of relative simple geometric entities, such as points, lines, and circles, and a small collection of constraints such as coincidence, tangency, and parallelity. For example, profile design for mechanical devices involves defining a closed perimeter curve, usually comprised of line segments and arcs, with a set of features, such as holes and slots, in the interior. In three dimensions, collections of simple solids (e.g., spheres, cones, cylinders) are combined to yield a solid structure. While the positions of the geometric entities in such structures often may be computed in a closed-form, analytic manner, the sequence of transformational operations required to satisfy the constraints may be quite complex. In the past, the designer of the part had to provide the transformation sequences. See, J. R. Rossignac, Constraints In Constructive Solid Geometry, In Proceedings of the 1986 Workshop on Interactive 3D Graphics, pages 93-110. ACM Press, 1986.
Texts in fields such as mechanical engineering or computer-aided design employ simple examples using algebraic techniques inspired by, and grounded in, the geometric nature of the problems being analyzed. Kinematic analysis of rigid-body mechanisms is an example in which geometric construction techniques are used. See, R. S. Hartenberg and J. Denavit. Kinematic Synthesis of Linkages. McGraw Hill, New York, 1964. However, real-world codes for kinematic analysis bear no resemblance to the human problem-solving techniques outlined in such texts, and are quite unintuitive.
The nonpatent references cited above are incorporated by reference for background.
U.S. patent application No. 07/365,586 and U.S. Pat. No. 5,043,959 introduced the concept of reasoning symbolically about geometric entities and constraints using a "degrees of freedom" approach. The present invention reflects a refinement and extension of this approach.